package offer;

/**
 * 剑指 Offer 12. 矩阵中的路径
 */
public class MatrixPath {

    private static final int[][] DIRECTIONS = { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };

    private int rows;
    private int cols;
    private int len;
    private char[][] board;
    char[] cs;
    private boolean[][] visit;

    public boolean exist(char[][] board, String word) {
        rows = board.length;
        cols = board[0].length;
        if (rows == 0) {
            return false;
        }
        visit = new boolean[rows][cols];
        len = word.length(); // 单词长度
        cs = word.toCharArray();
        this.board = board;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (backtracking(i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 回溯法
     * 
     * @param x     遍历索引x
     * @param y     遍历索引y
     * @param start word索引
     */
    public boolean backtracking(int x, int y, int start) {
        if (start == len - 1) {
            return board[x][y] == cs[start];
        }
        if (board[x][y] == cs[start]) {
            // 选择
            visit[x][y] = true;
            // 4个方向
            for (int[] dir : DIRECTIONS) {
                int newX = x + dir[0];
                int newY = y + dir[1];
                if (inArea(newX, newY) && !visit[newX][newY]) {
                    if (backtracking(newX, newY, start + 1)) {
                        return true;
                    }
                }
            }
            // 撤销选择
            visit[x][y] = false;
        }
        return false;
    }

    /**
     * 判断坐标是否越界
     */
    public boolean inArea(int x, int y) {
        return (x < rows && x >= 0) && (y >= 0 && y < cols);
    }
}
